18.5 スライディングビュー参照カウント法

スレッドの変更バッファをコレクタに転送する方法

世界を止めてヒープのスナップショットをとる

これまで見てきた手法

オンザフライでスレッドを1つずつ止める

オブジェクトの値がそれぞれ異なる時間に記録されてコレクタへ転送される

逐次的コンシステンシを仮定

ロックも不可分命令も使用しない

より弱いコンシステンシモデルをサポートするためにはアルゴリズムの変更が必要(詳細は後述)

コレクタとミューテータ間で4フェーズのハンドシェークを行って同調

Doligez and Gonthier(1994)と同様

さまざまな手法と組み合わせ可能

単純な参照カウント法(Levanoni and Petrank, 1999, 2001, 2006)

世代別コレクタ(Azatchi and Petrank, 2003)

年齢指向コレクタ(Paz et al., 2003, 2005b)

循環参照カウントコレクタ(Paz et al., 2005a, 2007)

年齢指向GC

年齢指向(age-oriented)コレクタはヒープを年少・年長世代に分割する

両世代は同時にGCされる

世代間ポインタをトラップしなくてよい

世代別に異なるポリシーと技法を選択

Paz et al.(2003)

年少世代

マークスイープ

低い生存率

年長世代

スライディングビュー参照カウント

低い死亡率・変更率

非移動型

各オブジェクトヘッダには世代を表すビットがある

アルゴリズム

スライディングビューの読み取りの合間にスロットが変更されて参照が失われることを防ぐ

code: アルゴリズム18-6.py

shared updates

def collect():

collectSlidingView()

# 年少世代のマークと年長世代の参照カウントの更新準備が整う

# on-the-fly handshake 4:

for each thread t:

suspend(t)

scanStack(t) # マークスイープや延期型参照カウント

resume(t)

# 年長世代から年少世代へのポインタの可能性があるので年長世代の処理が先

processReferenceCounts()

markNursery()

sweepNursery()

sweepZCT() # 年長世代は延期型参照カウント法と同じ方法で回収できる

# ダーティオブジェクトの参照カウントがゼロならログエントリから見つかる子孫の参照カウントをデクリメントする(図18-3)

collectCycles()

def collectSlidingView():

# on-the-fly handshake 1:

for each thread t:

suspend(t)

# 最初のハンドシェークの前に行うという記述と疑似コード(最初のハンドシェーク中に行う)とが矛盾する

tのバッファをupdatesへ転送 # 各スレッドを1つずつ止めて局所ログと年少集合をコレクタのupdatesバッファへ転送する

resume(t)

変更されたオブジェクトと年少オブジェクトをクリーンにする # クリーニングとの競合によってオブジェクトのダーティ状態が消される場合がある

# on-the-fly handshake 2:

for each thread t:

suspend(t)

変更-クリーンの衝突を見つける # 局所ログをオンザフライに走査してクリーニング中に変更されたオブジェクトを特定する

resume(t)

ダーティオブジェクトを確固たるものにする # 特定したオブジェクトのダーティ状態を復元する

# on-the-fly handshake 3:

for each thread t:

# 遅れたスレッドがいないことを保証する???

suspend(t)

resume(t)

def processReferenceCounts():

for each obj in updates:

decrementOld(obj)

incrementNew(obj)

# 年長世代から到達可能な年少オブジェクトの参照カウントが更新されるかもしれない

# そのオブジェクトがマークされていなければワークリストに加える

def collectCycles():

markCandidates()

markLiveBlack()

scan()

collectWhite()

processBuffers()

code: アルゴリズム18-7.py

me = myProcessorId

def Write(src, i, ref):

if src == Roots:

else:

if not dirty(src):

$ log(src)

snoop(ref) # スライディングビュー用

def log(ref):

for each fld in Pointers(ref):

if *fld != null:

if not dirty(ref):

# refがまだクリーンであればそのエントリをコミット

logPointer(ref) = entry

def snoop(ref):

# mySnoopedBufferの中身は非同期にワークリストへ転送される

code: アルゴリズム18-8.py

def New():

ref = allocate()

add(myYoungSet, ref)

setDirty(ref) # ライトバリアでlog(ref)が起動しないようにダーティとして割り付け

return ref

スライディングビュー循環参照GC

年齢指向コレクタは年長世代の循環参照を回収できない

Paz et al.(2007)はリサイクラーの循環参照GCアルゴリズムを組み合わせて回収する

非同期型リサイクラー

ヒープのトポロジーが変化して邪魔をするので難しい

スライディングビュー

変更のあったオブジェクトは記録されたログを使うことで固定したヒープのビューを与える

試験的削除アルゴリズムにおいて最初のパスの足取りを再追跡できる

スライディングビュー上の作業によりBacon and Rajan(2001)よりも単純な同期型アルゴリズムを採用できる

Pazらによる最適化

スカラオブジェクトは循環参照しない

2GCサイクルを生き延びた成熟オブジェクトの循環参照のみを考慮する

生きているかもしれないオブジェクトを考慮するのを避ける

メモリコンシステンシ

ここまでのスライディングビューアルゴリズムは逐次的コンシステンシを仮定している

近代のプロセッサは逐次的コンシステンシを必ずしも保証しない

ログに見られる値はGCサイクル開始前の値のスナップショット

コレクタは完成したログエントリだけを読み出す

弱いコンシステンシモデルのサポートのためにはさらに2つの修正が必要

ミューテータがライトバリア中のログ走査において同期を追加して、ポインタを変更するまえにログに記録する

コレクタ側にも同様の同期を追加する

効率が悪くなる

バッファの値群を局所配列に読み出してから処理することで同期コストを減らす